package leetcode;

/**
 * Created by tiang on 2018/11/23.
 * 将被围起来的0棋子修改为x棋子
 */
public class SurroundedRegions {
    /**
     * 只有与边界相连的节点是不可能被围起来的，所以从边界出发，将与边界相连的所有节点位置都标记为*，采用深度优先遍历
     * 之后将所有的O修改为X，将所有的*重新修改为O
     * @param board
     */
    public void solve(char[][] board) {
        if(board.length == 0)
            return;
        int row = board.length,
                col = board[0].length;
        for(int i=0;i<row;i++){
            dfs(board, i, 0);
            dfs(board, i, col-1);
        }
        for(int j=0;j<col;j++){
            dfs(board, 0, j);
            dfs(board, row-1, j);
        }
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(board[i][j] == '*')
                    board[i][j] = 'O';
                else if(board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }

    private void dfs(char[][] board, int x, int y){
        if(x<0||x>=board.length||y<0||y>=board[0].length)
            return;
        if(board[x][y] == 'X' || board[x][y] == '*')
            return;
        board[x][y] = '*';
        dfs(board, x-1, y);
        dfs(board, x+1, y);
        dfs(board, x, y+1);
        dfs(board, x, y-1);
    }
}
